class Edge:
    def __init__(self,to=1,w=0):
        self.to=to
        self.w=w
        self.source_edge=-1
class Solution:
    def foodTrans(self,n,m,k,need,edges):
        def addEdge(u,v):
            nonlocal cnt
            nonlocal pre
            nonlocal edge_list
            edge_list[cnt].to=v
            edge_list[cnt].source_edge=pre[u]
            pre[u]=cnt
            cnt+=1
        #表示从第start个节点出发，到达所有p[i]为1的节点的距离之和
        def getSum(start):
            nonlocal used
            num = pre[start]
            q=edge_list[pre[start]]
            res=0
            #讨论到单点
            if q.source_edge==-1:
                if not used[num//2]:
                    used[num//2]=True
                    res_flag=getSum(q.to)
                    res+=res_flag
                    if p[q.to]==1 or res_flag!=0:
                        res+=q.w
                    used[num//2]=False
                    return res
                else:
                    return 0
            while num!=-1:
                q=edge_list[num]
                if not used[num//2]:
                    used[num//2]=True
                    res_flag=getSum(q.to)
                    res+=res_flag
                    if p[q.to]!=0 or res_flag!=0:
                        res+=q.w
                    used[num//2]=False
                num=q.source_edge
            return res
        #表示从第i个节点出发，得到的最长距离
        def getLongest(start):
            nonlocal used
            res=0
            num=pre[start]
            q=edge_list[num]
            if q.source_edge==-1:
                if not used[num//2]:
                    used[num//2]=True
                    res_flag=getLongest(q.to)
                    used[num//2]=False
                    if p[q.to]==1 or res_flag!=0:
                        return res_flag+q.w
                    else:
                        return 0
            while num!=-1:
                q=edge_list[num]
                if not used[num//2]:
                    used[num//2]=True
                    temp=getLongest(q.to)
                    if p[q.to]==1 or temp!=0:
                        temp+=q.w
                    res=max(res,temp)
                    used[num//2]=False
                num=q.source_edge
            return res
        #1.g[v][u]表示从结点v开始出发，遍历所有u的子集的最短路径，min(g[v][S]),先遍历S,再遍历v。先找S最大的，再找v最小的
        # dp[1,T]=min(g[v][T])
        def calc(now):
            nonlocal p
            p=[0 for _ in range(n+1)]
            for i in range(1,n+1):
                if need[i]&(1<<now):
                    p[i]=1
            for i in range(1,n+1):
                g[i][1<<now]=(getSum(i)<<1) -getLongest(i)
            for i in range(1<<now):
                dp[1][i+(1<<now)]=float('inf')
                for j in range(1,n+1,1):
                    g[j][i+(1<<now)]=max(g[j][i],g[j][1<<now])
                    dp[1][i+(1<<now)]=min(dp[1][i+(1<<now)],g[j][i+(1<<now)])
        dp=[[0 for _ in range(1<<(k+1))] for _ in range(m+1)]
        p=[0 for _ in range(n+1)]
        g=[[0 for _ in range(1<<(k+1))] for _ in range(n+1)]
        used=[False]*(n-1)
        edge_list=list()
        cnt=0
        pre=[-1]*(n+1)
        for x,y,w in edges:
            edge_list.append(Edge(y,w))
            addEdge(x,y)
            edge_list.append(Edge(x,w))
            addEdge(y,x)
        for i in range(k):
            calc(i)
        for j in range(0,1<<k):
            for i in range(2,m+1):
                dp[i][j]=dp[1][j]
                s=j
                while s:
                    dp[i][j]=min(dp[i][j],max(dp[1][j-s],dp[i-1][s]))
                    s=(s-1)&j
        return dp[m][(1<<k)-1]
if __name__=='__main__':
    solution=Solution
    n,m,k=map(int,input().split())
    need=[0 for _ in range(n+1)]
    for i in range(1,n+1):
        in_temp=list(map(int,input().split()))
        for j in range(k):
            temp=in_temp[j]
            need[i]+=temp*(1<<j)
    edges=list()
    for i in range(n-1):
        edges.append(list(map(int,input().split())))
    res=solution.foodTrans(solution,n,m,k,need,edges)
    print(res)
# ————————————————
# 版权声明：本文为CSDN博主「Wumbuk」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# 原文链接：https://blog.csdn.net/qq_48081868/article/details/115425148